class Stack
{
public:
    Stack(int capacity = 4)
    {
        _a = (int*)malloc(sizeof(int)*capacity);
        _capacity =capacity;
        _top = 0;
    }
    Stack (const Stack& st)
    {
        _a = (int*)malloc(sizeof(int)*(st._capacity));
        memcpy(_a,st._a,sizeof(int)*(st._capacity));
        _top = st._top;
        _capacity = st._capacity;    
    }
    ~Stack()
    {
        if (_a)
        {
            free(_a);
            _a = NULL;
            _capacity = _top = 0;
        }
    }
    void push(int x)
    {
        if (_top == _capacity)
        {
            _capacity *= 2;
            int* ptr = (int*)realloc(_a,sizeof(int)*_capacity);
            if (ptr == NULL)
            {
                perror("realloc fail!\n");
                exit(-1);
            }
            _a = ptr;
        }
        _a[_top++] = x;
    }
    Stack& operator=(const Stack& st) 
    {
        _a = (int*)malloc(sizeof(int)*(st._capacity));
        memcpy(_a,st._a,sizeof(int)*(st._capacity));
        _top = st._top;
        _capacity = st._capacity;  
        return *this;       
    }
    void pop()
    {
        _top--;
    }
    int Top()
    {
        return _a[_top-1];
    }
    bool Empty()
    {
        return _top == 0;
    }
    int Size()
    {
        return _top;
    }
private:
    int* _a;
    int _top;
    int _capacity;
};

class MyQueue {
public:
    MyQueue() {

    }
    void push(int x) {
        _pushst.push(x);
    }
    
    int pop() {
        if (_popst.Empty())
        {
            in2out();
        }
        int ret = _popst.Top();
        _popst.pop();
        return ret;
    }
    
    int peek() {
        if (_popst.Empty())
        {
            in2out();
        }
        int ret = _popst.Top();
        return ret;        
    }
    
    bool empty() {
        return _pushst.Empty() && _popst.Empty();
    }
private:
    Stack _pushst;
    Stack _popst;

    void in2out()
    {
        while (!_pushst.Empty())
        {
            _popst.push(_pushst.Top());
            _pushst.pop();
        }
    }
};

